public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minSwapsCouples(new int[]{0, 3, 9, 4, 1, 2, 8, 5, 7, 6}));
    }

    public int minSwapsCouples(int[] row) {
        /**
         * 情侣牵手
         **/
        // 1 预处理
        int n = row.length;
        initialize();

        // 2 使用并查集查询无法匹配的组别
        for(int i = 0; i < n; i += 2) {
            int a = row[i] / 2;
            int b = row[i+1] / 2;
            if(a != b) {
                union(a, b);
            }
        }

        // 3 累加最小调整次数
        int ret = 0;
        for(int e: size) {
            ret += (e-1);
        }
        return ret;
    }

    // 创建并查集

    public static int MAX_N = 30;
    public static int[] father = new int[MAX_N];
    public static int[] size = new int[MAX_N];
    public static int[] stack = new int[MAX_N];

    public static void initialize() {
        /**
         * 初始化*/
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到a所在集合代表元素*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i>0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static void union(int a, int b) {
        /**
         * 合并集合*/
        // 1 找到集合代表元素
        int fa = find(a);
        int fb = find(b);

        // 2 小挂大
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                size[fb] = 1;
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                size[fa] = 1;
                father[fa] = fb;
            }
        }
    }
}
